package selected;

import java.util.ArrayList;
import java.util.List;

public class J0818 {
    // 1 最长连续1的个数
    public int longestOnes(int[] nums, int k) {
        // 也就是求窗口内最多有 k 个 0 的情况下，子串最大长度
        int left = 0, right = 0, count = 0, ret = 0, n = nums.length;
        while(right < n){
            // 进窗口
            int in = nums[right];
            if(in == 0) count++;
            while(count > k){
                // 出窗口
                if(nums[left++] == 0) count--;
            }
            // 更新结果
            ret = Math.max(right - left + 1, ret);
            right++;
        }
        return ret;
    }
    // 2 将 x 减到0的最小操作数
    public int minOperations(int[] nums, int x) {
        // 即就是 找到在数组中target = sum - x 的最大子数组长度
        int left = 0, right = 0, ret = -1, n = nums.length;
        int numSum = 0;
        for(int m : nums){
            numSum += m;
        }
        int target = numSum - x;
        if(target < 0) return -1;
        int sum = 0;
        while(right < n){
            // 进窗口
            sum += nums[right];
            // 判断
            while(sum > target){
                // 出窗口
                sum -= nums[left++];
            }
            // 更新结果
            if(sum == target) ret = Math.max(right - left + 1, ret);
            right++;
        }
        // 判断一下当前 ret 是否有效
        return ret == -1 ? -1 : n - ret;
    }
    // 3 水果成篮
    public int totalFruit(int[] fruits) {
        // count 只能 <= 2 的窗口最大是多少
        int[] hash = new int[100001];
        int left = 0, right  = 0, n = fruits.length, count = 0, ret = 0;
        while(right < n){
            // 进窗口
            int in = fruits[right];
            if(hash[in]++ == 0) count++;
            // 判断
            while(count > 2){
                // 出窗口
                int out  = fruits[left++];
                if(--hash[out] == 0) count--;
            }
            // 更新结果
            ret = Math.max(right - left + 1, ret);
            right++;
        }
        return ret;
    }
    // 4 字符串中所有字母异位词
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        // 核心就是使用两个 hash 数组记录字符出现的次数，再维护一个 count 来标记有效字符出现的次数
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        // 遍历出子串中所有字母出现的次数
        for(char c : pp){
            hash2[c - 'a']++;
        }
        for(int left = 0, right = 0, count = 0; right < ss.length; right++){
            // 进窗口
            char in = ss[right];
            if(++hash1[in - 'a'] <= hash2[in - 'a']) count++;
            // 判断
            while(right - left + 1 > pp.length){
                // 出窗口
                char out = ss[left++];
                if(hash1[out - 'a']-- <= hash2[out - 'a']) count--;
            }
            if(count == pp.length) ret.add(left);
        }
        return ret;
    }
    // 5 最小覆盖子串
    public String minWindow(String s, String t) {
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        int[] hash1 = new int[128];
        int[] hash2 = new int[128];
        // 使用kinds记录有效字符的种类
        int kinds = 0, minlen = Integer.MAX_VALUE, head = -1;
        for(char c : tt){
            if(hash2[c]++ == 0) kinds++;
        }
        for(int left = 0, right = 0, count = 0; right < ss.length; right++){
            // 进窗口
            char in = ss[right];
            if(++hash1[in] == hash2[in]) count++;   // 使用 count 记录窗口内有效字符的数量和种类，
            // 确保窗口内的有效字符与目标字符串对应
            while(count == kinds){  // 当字符的种类和数量完全相同时才可以更新结果
                if(minlen > right - left + 1){
                    head = left;
                    minlen = right - left + 1;
                }
                // 出窗口
                char out = ss[left++];
                if(hash1[out]-- == hash2[out]) count--;
            }
        }
        if(minlen == Integer.MAX_VALUE) return new String();
        String ret = s.substring(head, head + minlen);
        return ret;
    }
}
